- Title
- Leaf powers and their properties: using the trees
- Creator
- Fellows, Michael R.; Meister, Daniel; Rosamond, Frances A.; Sritharan, R.; Telle, Jan Arne
- Relation
- 19th International Symposium on Algorithms and Computation (ISAAC 2008). Algorithms and Computation: 19th International Symposium, ISAAC 2008 (Gold Coast, Qld 15-17 December, 2008) p. 402-413
- Publisher Link
- http://dx.doi.org/10.1007/978-3-540-92182-0_37
- Publisher
- Springer
- Resource Type
- conference paper
- Date
- 2008
- Description
- A graph G on n vertices is a k-leaf power (G ∈ Gk) if it is isomorphic to a graph that can be “generated” from a tree T that has n leaves, by taking the leaves to represent vertices of G, and making two vertices adjacent if and only if they are at distance at most k in T. We address two questions in this paper: (1) As k increases, do we always have Gk ⊆ Gk+1 ? Answering an open question of Andreas Brandstädt and Van Bang Le [2,3,1], we show that the answer, perhaps surprisingly, is “no.” (2) How should one design algorithms to determine, for k-leaf powers, if they have some property? One way this can be done is to use the fact that k-leaf powers have bounded cliquewidth. This fact, plus the FPT cliquewidth approximation algorithm of Oum and Seymour [14], combined with the results of Courcelle, Makowsky and Rotics [7], allows us to conclude that properties expressible in a general logic formalism, can be decided in FPT time for k-leaf powers, parameterizing by k. This is wildly inefficient. We explore a different approach, under the assumption that a generating tree is given with the graph. We show that one can use the tree directly to decide the property, by means of a finite-state tree automaton. (A more general theorem has been independently obtained by Blumensath and Courcelle [5].) We place our results in a general context of “tree-definable” graph classes, of which k-leaf powers are one particular example.
- Subject
- k-leaf powers; graphs; tree; graph classes
- Identifier
- http://hdl.handle.net/1959.13/802547
- Identifier
- uon:6126
- Identifier
- ISBN:9783540921813
- Language
- eng
- Reviewed
- Hits: 3668
- Visitors: 3581
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|